import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr.copy()
    
    arr_copy = arr.copy()
    _quick_sort(arr_copy, 0, len(arr_copy)-1)
    return arr_copy

def _quick_sort(arr, low, high):
    if low < high:
        pivot_idx = partition(arr, low, high)
        _quick_sort(arr, low, pivot_idx-1)
        _quick_sort(arr, pivot_idx+1, high)

def partition(arr, low, high):
    # Random pivot selection to avoid worst-case behavior
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    pivot = arr[high]
    
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1